1. Field
The present invention relates generally to computer graphics and, more specifically, to spatial partitioning of a two-dimensional (2D) or three-dimensional (3D) scene.
2. Description
In 2D and 3D computer graphics, spatial partitioning typically includes the action of dividing up a space into smaller portions. The space may represent a scene in a world. The portions are sometimes called octants (for 3D), quadrants (for 2D), or gridlets (for 2D or 3D). Subdividing space is usually done during graphics pipeline processing to minimize future computation and to minimize the number of objects sent down the graphics pipeline. For example, if some objects in the scene are not currently visible based on the current camera position, then there is no need to further process these objects. Instead of examining each object submitted into the pipeline, when using spatial partitioning, graphics processing examines only the octants actually containing objects of the scene. For example, entire octants may be removed from further processing consideration if they are outside of the currently visible region of the scene, thus saving the time of transforming, rendering, and rasterizing the polygons of the objects contained in the non-visible octants.
Once a scene is partitioned and all objects in the scene are identified for a particular portion of the space, the results are typically stored in a data structure for subsequent use by graphics processing components (such as a video game engine or an animation generator, for example). This data structure is usually generated after scene creation, but before scene visualization and user interaction with the scene. During scene visualization, it may be necessary to find an object in the scene corresponding to a selected point. Given a point in 2D coordinates (e.g., x, y) or 3D coordinates (e.g., x, y, z), the data structure is typically traversed to find information about the object containing the point.
There are at least several existing techniques and corresponding data structures for spatial partitioning. These include uniform grids (also called regular grids), binary space partitioning (BSP) trees, octrees, and k-d trees. Each technique has its own advantages and disadvantages.
A uniform grid is the simplest spatial partitioning scheme. A grid is uniformly subdivided and superimposed onto the scene. For example, if the space is 10 units by 10 units by 10 units, the space could be partitioned into 1 unit by 1 unit by 1 unit cubes (e.g., octants). Advantages of this technique include predictable and relatively fast speed for traversal of the data structure when there is a reasonably uniform distribution of objects in the scene, and fast speed to insert an object into the scene. One drawback is that dense and sparse areas of the scene are presented with identical subdivision. The consequence is that grid cells in densely populated areas contain a high amount of objects while grid cells in sparse areas are nearly empty. As a result, a uniform grid is efficient only if the scene contents are uniformly distributed. Hence, a uniform grid solution partitions the space poorly and doesn't take into account how objects are placed in the scene. Uniform grids are most suited for dynamic scenes.
A BSP tree is a data structure used when recursively dividing space into pairs of subspaces, each separated by a plane of arbitrary orientation and position. Partitions usually focus on polygons of static objects in the scene. Non-uniform partitioning is accomplished by positioning partition planes depending on where objects are located. The BSP tree is typically not axis-aligned and objects may be split by the partitioning planes. Splitting creates a considerable amount of sub-polygons. This technique is suitable for static scenes. However, for a dynamic scene, the data structure must be reconstructed, which is very time consuming and is inadequate for real-time applications such as a video game or an interactive 3D website.
An octree is a data structure similar to a binary tree, but having a greater number of child nodes per parent node. Whereas a binary tree node typically has two child nodes (e.g., left and right children), an octree node has a specified number of child nodes (such as eight). Each node of the octree represents an octant of the scene. Each octant is sub-divided into a number of sub-octants (e.g., eight). Each node of the data structure contains pointers to the octants contained inside (e.g., a parent node points to child nodes). For 2D scenes, the tree is called a quadtree. For 3D scenes, the tree is a called an octree. Finer subdivision is performed in densely populated areas. If no objects are in an octant, then the octant is not subdivided further. An octree may be uniformly or non-uniformly subdivided, depending on the spatial partitioning algorithm used. The octree hierarchically partitions space up to a specified depth. Octrees provide better overall results than the uniform grid based scheme, but partitioning can be poor if objects lie on partitioning planes. Scene traversal for octrees is more expensive than with uniform grids. The octree adapts slowly to irregular scene structure. Another disadvantage is that partitioning with octrees tends to cluster objects at higher levels of the tree. When traversing the octree in a dynamic scene, tree traversal may be slow due to this high level clustering effect.
A k-d tree is a generalization of a binary tree where k is the dimension of the tree and d stands for dimension. For spatial partitioning, a k-d tree may be used to divide space. For example, each division of space denotes which side of a line (in 2D) or a plane (in 3D) an object may be on. Each time the left side of a line (or plane) or below a line (or plane) is considered, a left node of the k-d tree is examined. Each time the right side (or plane) or above a line (or plane) is considered, a right node of the k-d tree is examined. This process may be continued until a predetermined depth of the k-d tree is reached. One disadvantage of k-d trees is there is no predicatability. If objects move, the partitioning will not be effective.
Many game engines use a BSP tree or a k-d tree for spatial partitioning. Both of these algorithms construct a spatial hierarchical data structure in a computationally expensive preprocessing stage. If any objects move in the scene, the spatial hierarchical data structure becomes outdated, possibly resulting in incorrect results for queries. One solution to this problem is to update and reinitialize the data structure. However, reconstructing the BSP tree or k-d tree is a very time consuming process that renders these techniques unsuitable for use in processing a dynamic scene.
Although various techniques exist for spatial partitioning, none of the above-described techniques perform optimally in a variety of settings. Techniques that work well for static scenes perform poorly for dynamic scenes. What is needed is a technique and corresponding data structure that performs well for both static and dynamic scenes.